import common.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 637. Average Of Levels In Binary Tree 二叉树的层平均值
 * https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/
 */
class AverageOfLevelsInBinaryTree {
    /**
     * 方法： 使用广度优先搜索计算二叉树每层的平均值
     * 
     * Args:
     *   root: TreeNode - 二叉树的根节点
     * 
     * Returns:
     *   List<Double>: 包含每层节点平均值的列表
     * 
     * Time: O(n) - 其中n是二叉树的节点数，每个节点只被访问一次
     * 
     * Space: O(w) - 其中w是二叉树的最大宽度，队列中最多存储一层的所有节点
     */
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> ans = new ArrayList<>();
        Deque<TreeNode> q = new LinkedList<>();
        q.addLast(root);
        while(!q.isEmpty()){
            int len = q.size();
            long sum = 0l;
            for(int i = 0; i < len; i++){
                TreeNode node = q.removeFirst();
                sum += node.val;
                if(node.left != null){
                    q.addLast(node.left);
                }
                if(node.right != null){
                    q.addLast(node.right);
                }
            }
            ans.add(sum * 1.0 / len);
        }
        return ans;
    }
}